package q538_convertBST;

import CommonClass.Common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_1 {

    /**
     * 此题实际上就是把我们的中序遍历改为 右 中 左 来解决问题
     * 我们只需要先遍历到最右边的节点 然后节点值改为当前节点值 + 上个节点值
     * 即可解决
     * 注意更新上个节点值即可
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new LinkedList<>();

        int prev = 0;
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            // 右
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            // 中
            node = stack.pop();
            node.val = node.val + prev;
            prev = node.val;

            // 左
            node = node.left;
        }

        return root;

    }
}
